﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <iomanip>

using namespace std;


class Solution {
public:
    vector<int> findDiagonalOrder(vector<vector<int>>& mat) {
        int i = 0, j = 0;//起始位置
        int n = mat.size(), m = mat[0].size();//边界位置

        vector<int> ret;//储存返回序列
        bool toward = true;//定义方向，true表示右上，false表示左下 

        //利用斜对角和为定值的特性
        for (int sum = 0; sum <= n + m - 2; sum++)
        {
            if (toward)
            {
                i = (sum > n - 1) ? n - 1 : sum;//这里处理长方形情况
                j = sum - i;
                while (i + j == sum && i >= 0 && j < m)//防止越界
                {
                    ret.push_back(mat[i][j]);
                    i--;
                    j++;
                }
                toward = false;
            }
            else
            {
                j = (sum > m - 1) ? m - 1 : sum;//这里处理长方形情况
                i = sum - j;
                while (i + j == sum && j >= 0 && i < n)//防止越界
                {
                    ret.push_back(mat[i][j]);
                    j--;
                    i++;
                }
                toward = true;
            }
        }

        return ret;
    }
};


int main()
{
	return 0;
}